// https://www.lintcode.com/problem/arrange-interview-city/

public class Solution {
    /**
     * @param cost: The cost of each interviewer
     * @return: The total cost of all the interviewers.
     */
    public int TotalCost(List<List<Integer>> cost) {
        // write your code here
        int ret = 0;
        List<Integer> diff = new ArrayList<>();
        for (List<Integer> c : cost) {
            ret += c.get(1);
            diff.add(c.get(0) - c.get(1));
        }
        Collections.sort(diff);
        for (int i = 0; i < (diff.size() / 2); ++i) {
            ret += diff.get(i);
        }
        return ret;
    }
}